/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 三石
 * Date: 2022-08-23
 * Time: 22:49
 */
public class LinstNode {
    /**
     * 定义一个节点Node，其中包含两部分
     */
    static class Node{
       public int val;
       public Node next;
       
        //构造方法
       public Node(int val){
           this.val=val;
       }
    }
    public Node head;


    public void creatlist(){
        Node node1=new Node(13);
        Node node2=new Node(23);
        Node node3=new Node(55);
        Node node4=new Node(63);
        Node node5=new Node(75);
        head=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        //node5.next=node3;
        //node5.next=head;

    }

    /**
     * 计算链表长度
     */
    public int size(){
        Node cur=head;
        int count=0;
        while (cur != null){
            count++;
            cur=cur.next;
        }
        return count;
    }

    public void display(){
        Node cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }

    /**
     * 查找关键字key是否存在
     * @param key
     * @return
     */
    public boolean find(int key){
        Node cur=head;
        while (cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    public void delete(int n){
        Node cur=head;

        while (cur!=null){
            cur=cur.next;
            if(cur.val==n) {
                Node M = cur.next;
                while (M != null) {
                    cur.val = M.val;
                    cur.next = M.next;
                    M = M.next;
                    cur=cur.next;
                }
            }
        }
    }

    /**
     * 头插
     * @param date
     */
    public void addfirst(int date){
        Node node=new Node(date);
        node.next=head;
        head=node;
    }

    /**
     * 尾插
     * @param val
     */
    public void addend(int val){
        Node node=new Node(val);
        Node cur=head;
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }

    /**
     * 任意位置插入
     * @param num
     * @param m
     */
    public void add(int num, int m){
        Node cur=head;
        Node node1=new Node(num);
        int sum=0;
        while (cur!=null){
            sum++;
            cur=cur.next;
           if (sum==m){
               Node N=cur.next;
               cur.next=node1;
               node1.next=N;
           }
        }
    }

    /**
     * 删除第一个key
     */
    public void dell(int key){
        if(head.val==key){
            head=head.next;
        }else {
            Node cur=head.next;
            Node P=head;
            while (cur!=null){
                if(cur.val==key){
                    P.next=cur.next;
                    return;
                }
                P=P.next;
                cur=cur.next;
            }
        }
    }

    /**
     * 删除所有key节点
     */
    public void dellAll(int key){
        Node cur=head.next;
        Node P=head;
        while (cur!=null){
            if(cur.val==key){
                P.next=cur.next;
                cur=cur.next;
            }else {
                P=P.next;
                cur=cur.next;
            }
        }
           if(head.val==key){
               head=head.next;
           }
    }

    /**
     * 清空所有节点
     */
    public void free(){
        Node cur=head;
        while (cur!=null){
            Node P=cur.next;
            cur =null;
            cur=P;
        }
        head=null;
    }

    /**
     * 链表转置
     */
    public Node Transpose(){
        if (head==null)  return null;
        if (head.next==null)  return head;

        Node cur=head.next;
        head.next=null;
        while (cur!=null){
            Node curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return  head;
    }

    /**
     * 找倒数第k个
     */
    public int findk( int n){
        if (n<=0||head==null){
            return -1;
        }
        Node fast=head;
        Node slow=head;
        int sum=1;
        while (sum<=n-1){
            fast=fast.next;
            if (fast==null){
                return -1;
            }
            sum++;
        }
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        System.out.println(slow.val);
        return slow.val;
    }

    /**
     * 找中间节点坐标
     */
    public int findmiddle(){
        int count=0;
        Node fast=head;
        Node slow=head;
        while (fast != null && fast.next != null){
            slow=slow.next;
            fast=fast.next.next;
            count++;
        }
        return count;
    }

}
